package com.leetcode.动态规划;

import java.util.ArrayList;
import java.util.List;

public class L139单词拆分 {
	public static void main(String[] args) {
		String s;
		List<String> wordDict = new ArrayList<String>();
		s = "applepenapplepen";
		System.out.println(s.substring(1, 3));
		wordDict.add("apple");
		wordDict.add("pen");
		boolean b = new Sulotion139().wordBreak(s, wordDict);
		System.out.println(b);
	}
}

class Sulotion139 {
	public boolean wordBreak(String s, List<String> wordDict) {
		boolean[] dp = new boolean[s.length() + 1];
		for (int j = 1; j < dp.length; j++) {//遍历背包
			for (int i = 0; i < wordDict.size(); i++) {//遍历物品，这样的遍历顺序是为了保证重复遍历物品
				if (j - wordDict.get(i).length() >= 0) {
					//当前遍历的单词如果位于开头
					if (j == wordDict.get(i).length())
						dp[j] = s.startsWith(wordDict.get(i)) ? true : dp[j];
					
					else if (s.substring(j - wordDict.get(i).length(), j).equals(wordDict.get(i)))
						dp[j] = dp[j - wordDict.get(i).length()] ? true : dp[j];
					
					//dp[j]为true,说明可以用wordDict里的单词组成长度为j的字符串，就不用再重复判断了
					if(dp[j]) break; 
					
				}

			}
		}
		return dp[s.length()];
	}
}